package dp;

import org.junit.Test;

import java.util.Arrays;

public class MininumInsertionToMakePalindrome1312 {

    @Test
    public void test() {
        minInsertions("zzazz");
        minInsertions("mbadm");
        minInsertions("leetcode");
        minInsertions("g");
        minInsertions("no");
    }

    public int minInsertions(String s) {
        // dp[i][j] 表示让 s[i..j] 变成回文的最小插入数量
        // base case 是 s[i][i] = 0;
        // 结果是 s[0..n]
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0 ; i < dp.length; i++) {
            Arrays.fill(dp[i], 0);
        }

        for (int k = 2; k <= s.length(); k++) {
            for (int i = 0; i <= s.length()-k; i++) {
                int j = i + k - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = Math.min(
                            dp[i+1][j]+1, //在s[i+1,j]已经变为回文串的基础上,又多了个s[i],所以需要在s[j]左侧增加一个
                            dp[i][j-1]+1);//类似
                }
            }
        }
        System.out.format("s: %s, min: %d\n", s, dp[0][s.length()-1]);
        return dp[0][s.length()-1];
    }

    // 以下思路是错的, 不能这样定义dp[i][j]
    public int minInsertionsWrong(String s) {
        // dp[i][j] 表示让 s[0..i] 到 s[j..] 变成回文的最小代价, 其中, 0<=i<=j<=s.length-1
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0 ; i < dp.length; i++) {
            Arrays.fill(dp[i], 0);
        }

        dp[0][s.length()-1] = (s.charAt(0) == s.charAt(s.length()-1)) ? 0 : 1;
        for (int j = s.length()-2; j >= 0; j++) {
            int len = s.length()-j;
            dp[0][j] = Math.min(len, dp[0][j+1]);
        }

        for (int k = s.length()-1; k >= 0; k--) {
            for (int i = 0 ; i < s.length() - k; i++) {
                int j = i + k;
                // 以 i 或 j 为核心

                int min;
                if (i-1 >= 0 && j+1 < s.length()) {
                    min = dp[i - 1][j + 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
                } else {
                    min = (s.charAt(i) == s.charAt(j) ? 0 : 1);
                }

//                // 以 i 为核心
//                if (i-1 >= 0) {
//                    min = Math.min(min, dp[i - 1][j]+1);
//                }
//
//                // 以 j 为核心
//                if (j+1 < s.length()) {
//                    min = Math.min(min, dp[i][j + 1]+1);
//                }

                dp[i][j] = min;
            }
        }

        return 0;
    }
}
